/**
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 **k** 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：k = 2, prices = [2,4,1]
输出：2
 */


/**
 * dp[j] j=2*k+1
 * 奇数 持有状态 初始状态都是-prices[0]
 * 偶数 不持有状态
 */
var maxProfit = function (k, prices) {
  const dp = Array(2 * k + 1).fill(0);
  //init
  for (let j = 1; j < 2 * k + 1; j += 2) {
    dp[j] = -prices[0];
  }
  for (let i = 1; i < prices.length; i++) {
    for (let j = 1; j < 2 * k + 1; j++) {
      dp[j] = Math.max(dp[j], dp[j - 1] + (j & 1 ? -prices[i] : prices[i]));
    }
  }
  return dp[2 * k];
};
console.log('买卖股票-买卖k次',maxProfit(2, [2, 4, 1])); //2